package LeetCode;

import java.util.List;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}21:19
 */
public class LeetCode92 {
    public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }
    //方法一：递归反转整个链表
//    public ListNode reverseBetween(ListNode head, int m, int n) {
//        if (m == 1){
//
//        }
//    }
    //方法二：双指针-头插法
    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode pre = new ListNode(0);
        pre.next = head;
        //定义双指针
        ListNode left = pre;
        ListNode right = pre.next;

        //将双指针移动到要进行翻转的地方
        for (int i = 0; i < m - 1; i++){
            left = left.next;
            right = right.next;
        }

        //进行翻转
        for (int i = 0; i < n - m; i++){
            ;ListNode re = right.next;
            right.next = right.next.next;//进行了删除
            re.next = left.next;
            left.next = re;
        }
        return pre.next;

//        ListNode dummyHead = new ListNode(0);
//        dummyHead.next = head;
//        //双指针
//        ListNode l = dummyHead;
//        ListNode r = dummyHead.next;
//
//        int step = 0;
//        //将这两个指针移动到要反转的部分
//        while (step < m - 1){
//            l = l.next;
//            r = r.next;
//            step++;
//        }
//
//        for (int i = 0; i < n - m; i++){//进行一个头插法来反向移动
//            ListNode removerd = r.next;
//            r.next = r.next.next;
//            removerd.next = l.next;
//            l.next = removerd;
//        }
//
//        return dummyHead.next;
    }

}
